/*94.二叉树的中序遍历 */
function TreeNode(val, left, right) {
	this.val = val == null ? 0 : val
	this.left = left == null ? null : left
	this.right = right == null ? null : right
}
/* 
    中序遍历:按照左子树 => 根节点 => 右子树 的方式遍历这棵树
*/
var inorderTraversal = function (root) {
	const res = []
	const inorder = (root) => {
		if (!root) return
		inorder(root.left)
		res.push(root.val)
		inorder(root.right)
	}

	inorder(root)
	return res
}

/* 迭代:显示维护一个栈 */
var inorderTraversal = function (root) {
	const res = []
	const stack = []
	while (root || stack.length) {
		while (root) {
			stack.push(root)
			root = root.left
		}
		root = stack.pop()
		res.push(root.val)
		root = root.right
	}
	return res
}
/* 
    Morris 中序遍历 
    它能将非递归的中序遍历空间复杂度讲到O(1)
    当前节点:x
    1.如果x无左孩子，先将x的值加入答案数组，再访问x的右孩子 即x = x.right
    2.如果x有左孩子，则找到x的左子树上的最右的节点【即左子树中序编列的最后一个节点
    x在中序编中的前驱点】我们记为 temp 根据temp 的右孩子是否为空，进行如下操作

    如果 temp 的右孩子为空 则将其右孩子指向x，然后访问 x的左孩子，即x = x.left
    如果temp 的右孩子不为空,则此时其右孩子指向x,说明我们已经遍历完x的左子树，
    我们将temp 的右孩子置空，将x的值加入答案数组，然后访问x的右孩子，即x = x.right

    重复以上操做
*/

var inorderTraversal = function (root) {
	const res = []
	let predecessor = null //前驱点

	while (root) {
		if (root.left) {
			// predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
			predecessor = root.left
			while (predecessor.right && predecessor.right !== root) {
				predecessor = predecessor.right
			}
			/* 让predecessor 的右指针指向根节点，继续遍历左子树 */
			if (!predecessor.right) {
				predecessor.right = root
				root = root.left
			} else {
				// 说明左子树已经访问完了我们需要断开链接
				res.push(root.val)
				predecessor.right = null
				root = root.right
			}
		} else {
			// 如果没有左孩子，直接访问右孩子
			res.push(root.val)
			root = root.right
		}
	}
}
